{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-230630b07a6bced0",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "# Exercise 3: Dynamic Programming\n",
    "\n",
    "## 1) Policy Evaluation\n",
    "\n",
    "After your master thesis you decide to study on and do you beer-bachelor.\n",
    "Therefore, you have to drink three beers in three different pubs. \n",
    "There are six pubs available in town, you start at home and will (hopefully) end up at home. The problem is depicted in the following picture:\n",
    "\n",
    "![](Beer-Bachelor.png)\n",
    "\n",
    "In our first example we follow the 50/50 policy. \n",
    "So after drinking in a pub - e.g. Auld Triangle, there is a $50 \\, \\%$ probability to go \"up\" to the Globetrotter and  $50\\, \\%$ probability to go \"down\" to the Black Sheep.\n",
    "Evaluate the state values using policy evaluation ($v_\\mathcal{X} = \\mathcal{R}_\\mathcal{X} + \\gamma \\mathcal{P}_{xx'} v_\\mathcal{X}$):\n",
    "\n",
    "\\begin{align*}\n",
    "\\begin{bmatrix}\n",
    "v^{50/50}_{1}\\\\\n",
    ".\\\\\n",
    ".\\\\\n",
    ".\\\\\n",
    "v^{50/50}_{n}\\\\\n",
    "\\end{bmatrix}\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "\\mathcal{R}^{50/50}_{1}\\\\\n",
    ".\\\\\n",
    ".\\\\\n",
    ".\\\\\n",
    "\\mathcal{R}^{50/50}_{n}\\\\\n",
    "\\end{bmatrix}\n",
    "+\n",
    "\\gamma\n",
    "\\begin{bmatrix}\n",
    "{p}^{50/50}_{11}&...&{p}^{50/50}_{1n}\\\\\n",
    ".& &.\\\\\n",
    ".& &.\\\\\n",
    ".& &.\\\\\n",
    "{p}^{50/50}_{n1}&...&{p}^{50/50}_{nn}\\\\\n",
    "\\end{bmatrix}\n",
    "\\begin{bmatrix}\n",
    "v^{50/50}_{1}\\\\\n",
    ".\\\\\n",
    ".\\\\\n",
    ".\\\\\n",
    "v^{50/50}_{n}\\\\\n",
    "\\end{bmatrix}\n",
    "\\end{align*}\n",
    "\n",
    "The rewards are given as negative numbers next to the arrows and represent the distances between two bars as a penalty.\n",
    "In this exercise we will set $\\gamma = 0.9$. \n",
    "In the shown problem we have $n = 8$ states (pubs, including start-home and end-home), ordered as given by the state space:\n",
    "\n",
    "\\begin{align*}\n",
    "\\mathcal{X} =\n",
    "\\left\\lbrace \\begin{matrix}\n",
    "\\text{Start: Home}\\\\\n",
    "\\text{Auld Triangle}\\\\\n",
    "\\text{Lötlampe}\\\\\n",
    "\\text{Globetrotter}\\\\\n",
    "\\text{Black Sheep}\\\\\n",
    "\\text{Limericks}\\\\\n",
    "\\text{Fat Louis}\\\\\n",
    "\\text{End: Home}\\\\\n",
    "\\end{matrix}\n",
    "\\right\\rbrace\n",
    "\\end{align*}\n",
    "\n",
    "Use a little python script to calculate the state values!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": true,
     "grade_id": "cell-16d89aafe7b794c3",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "## 1) Solution\n",
    "\n",
    "The state transition matrix is given by:\n",
    "\n",
    "$\\mathcal{P}_{xx'} = \n",
    "\\begin{bmatrix}\n",
    "0 & 0.5 & 0.5 & 0 & 0 & 0 & 0 & 0\\\\\n",
    "0 & 0 & 0 & 0.5 & 0.5 & 0 & 0 & 0\\\\\n",
    "0 & 0 & 0 & 0.5 & 0.5 & 0 & 0 & 0\\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0.5 & 0.5 & 0\\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0.5 & 0.5 & 0\\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\\\\n",
    "\\end{bmatrix}\n",
    "$\n",
    "\n",
    "By matrix inversion we can calculate the state values for the given policy like already learned in exercise 2 by:\n",
    "\\begin{align}\n",
    "v_\\mathcal{X} &= \\mathcal{R}_\\mathcal{X} + \\gamma \\mathcal{P}_{xx'} v_\\mathcal{X}\\\\\n",
    "v_\\mathcal{X} - \\gamma \\mathcal{P}_{xx'} v_\\mathcal{X} &= \\mathcal{R}_\\mathcal{X}\\\\\n",
    "\\left( I_8 - \\gamma \\mathcal{P}_{xx'} \\right) v_\\mathcal{X} &= \\mathcal{R}_\\mathcal{X}\\\\\n",
    "v_\\mathcal{X} &= \\left( I_8 - \\gamma \\mathcal{P}_{xx'} \\right)^{-1} \\mathcal{R}_\\mathcal{X}\\\\\n",
    "\\end{align}\n",
    "\n",
    "First, we have to calculate the expected reward using the 50/50 policy. \n",
    "Concerning the home state, it is 50 % likely to receive a negative reward of -3 on the way to the Auld Triangle and 50 % likely to receive a negative reward of -1 on the way to Lötlampe. \n",
    "So the expected reward is given by: $\\mathcal{R}_1 = 0.5 \\cdot (-3) + 0.5 \\cdot (-1) = -2$\n",
    "\n",
    "Following this concept, the expected reward vector is given by:\n",
    "\n",
    "$\\mathcal{R} =\n",
    "\\begin{bmatrix}\n",
    "-2\\\\\n",
    "-3\\\\\n",
    "-4\\\\\n",
    "-4.5\\\\\n",
    "-5.5\\\\\n",
    "-6\\\\\n",
    "-7\\\\\n",
    "0\n",
    "\\end{bmatrix}\n",
    "$\n",
    "\n",
    "Making use of this knowledge, we can calculate the state values as follows:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-c8311eb3e04caeaf",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[-13.9385]\n",
      " [-12.765 ]\n",
      " [-13.765 ]\n",
      " [-10.35  ]\n",
      " [-11.35  ]\n",
      " [ -6.    ]\n",
      " [ -7.    ]\n",
      " [  0.    ]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "# define given parameters\n",
    "gamma = 0.9 # discount factor\n",
    "\n",
    "### BEGIN SOLUTION\n",
    "\n",
    "P_xx = np.array([[0, 0.5, 0.5,   0,   0,   0,   0,   0],\n",
    "                 [0,   0,   0, 0.5, 0.5,   0,   0,   0],\n",
    "                 [0,   0,   0, 0.5, 0.5,   0,   0,   0],\n",
    "                 [0,   0,   0,   0,   0, 0.5, 0.5,   0],\n",
    "                 [0,   0,   0,   0,   0, 0.5, 0.5,   0],\n",
    "                 [0,   0,   0,   0,   0,   0,   0,   1],\n",
    "                 [0,   0,   0,   0,   0,   0,   0,   1],\n",
    "                 [0,   0,   0,   0,   0,   0,   0,   1]]) # state trasition probability\n",
    "\n",
    "r_X = np.array([-2, -3, -4, -4.5, -5.5, -6, -7, 0]) # rewards\n",
    "r_X = r_X.reshape(-1, 1) # make column vector\n",
    "\n",
    "v_X = np.matmul(np.linalg.inv(np.eye(8)-gamma*P_xx) , r_X)\n",
    "\n",
    "### END SOLUTION\n",
    "\n",
    "print(v_X)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-707636577622b626",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## 2) Exhaustive Policy Search \n",
    "\n",
    "From now on use $\\gamma = 1$.\n",
    "\n",
    "As you have pre knowledge from your master degree, you try to minimize the distance of the way you have to take during your tour in order to have more time in the pubs. Therefore, you perform the following exhaustive search algorithm:\n",
    "\n",
    "1. Write down all possible path-permutations and calculate the distances.\n",
    "2. Which is the best path concerning most beer per distance?\n",
    "3. Derive the formula to calculate the number of necessary path comparisons. \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": true,
     "grade_id": "cell-e069b4ff0546056a",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "## 2) Solution\n",
    "\n",
    "Auld Triangle, Globetrotter, Limericks = -15\n",
    "\n",
    "Auld Triangle, Globetrotter, Fat Louis = -17\n",
    "\n",
    "Auld Triangle, Black Sheep, Limericks = -18\n",
    "\n",
    "Auld Triangle, Black Sheep, Fat Louis = -20\n",
    "\n",
    "Lötlampe, Black Sheep, Fat Louis = -19\n",
    "\n",
    "Lötlampe, Black Sheep, Limericks = -17\n",
    "\n",
    "Lötlampe, Globetrotter, Limericks = -14\n",
    "\n",
    "Lötlampe, Globetrotter, Fat Louis = -16\n",
    "\n",
    "Choice of two, three times. Order of chosen actions $\\{up, down\\}$ is important and number of choices stays the same. The number of different paths is therefore given by: $N^k = 2^3 = 8$. So the number of necessary path comparisons is $N^k -1 = 2^3 -1= 7$.\n",
    "\n",
    "With number of decisions $k$ and possible options per decision $N$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-c82401280b863042",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## 3) Dynamic Programming - The Idea\n",
    "\n",
    "Trying out all combinations might not be best for your liver, so you want to solve the problem above using dynamic programming. \n",
    "\n",
    "Making use of value iteration, derive the values resulting from the optimal policy: $v_{i+1}^*(x_k) = \\text{max}_u (r_{k+1} + v_{i}^*(x_{k+1}))$.\n",
    "\n",
    "Hint: There is only one policy improvement step needed.\n",
    "\n",
    "How many value comparisons have to be made?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": true,
     "grade_id": "cell-d0d9f6387127340b",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "## 3) Solution\n",
    "\n",
    "In this situation, we are looking for the state with maximum value denoted by the asterisk $^*$.\n",
    "At first we initialize all state values with zero and update from start to end using the equation above. \n",
    "\n",
    "For the first iteration $i=0$, all state values are zero, so for $i=1$, the best immediate reward is taken as new state value due to $v_{i=1}^*(x_k) = \\text{max}_u (r_{k+1} + \\underbrace{v_{i=0}^*(x_{k+1}))}_{=0}$.\n",
    "\n",
    "For $i=2$ we have to consider that the state value $v_{i=1}^*(x_{k+1})$ is not zero anymore.\n",
    "\n",
    "For example for the \"Start\" state we have the options: \n",
    "1. To A: $v_{i=2}(Start) = -3 -2 = -5$\n",
    "2. To Lö:$v_{i=2}(Start) = -1 -3 = -4$\n",
    "\n",
    "As we are looking for the optimal policy (remember $^*$) we take the better value (to Lö).\n",
    "\n",
    "For the state A we have the options: \n",
    "1. To G: $v_{i=2}(A) = -2 -4 = -6$\n",
    "2. To B: $v_{i=2}(A) = -4 -5 = -9$\n",
    "\n",
    "...\n",
    "\n",
    "i \\ x   | Start  |   A    |  Lö    |   G    |   B    |  Li    |   F    |  End\n",
    "-------- | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ \n",
    "    0    |   0    |   0    |   0    |   0    |   0    |   0    |   0    |   0\n",
    "    1    |   -1   |   -2   |   -3   |   -4   |   -5   |   -6   |   -7   |   0\n",
    "    2    |   -4   |   -6   |   -7  |   -10   |   -11   |   -6   |   -7   |   0\n",
    "    3    |   ...   |   \n",
    "\n",
    "This would take a lot of time and it would be better to write a little programm.\n",
    "But if we change the order of state updates in a clever way, like explained in the lecture, it needs only one iteration to find the result!\n",
    "\n",
    "Since we know the model, we are able to begin the evaluation in the end state and can derive the final state values directly: \n",
    "\n",
    "If in Limericks or Fat Louis, there is no choice of way, so the value of these locations is directly given.\n",
    "\n",
    "\\begin{align}\n",
    "v(\\text{Limericks})&=-6\\\\\n",
    "v(\\text{Fat Louis})&=-7\n",
    "\\end{align}\n",
    "\n",
    "If in Globetrotter or Black Sheep, the choice where to go is determined by the distance and the future value:\n",
    "\n",
    "\\begin{align}\n",
    "v(\\text{Globetrotter})&=-4+v(\\text{Limericks})=-10 \\hspace{0.5cm} \\Leftarrow \\text{optimal choice}\\\\\n",
    "v(\\text{Globetrotter})&=-5+v(\\text{Fat Louis})=-12\n",
    "\\end{align}\n",
    "\n",
    "\\begin{align}\n",
    "v(\\text{Black Sheep})&=-5+v(\\text{Limericks})=-11 \\hspace{0.5cm} \\Leftarrow \\text{optimal choice}\\\\\n",
    "v(\\text{Black Sheep})&=-6+v(\\text{Fat Louis})=-13\n",
    "\\end{align}\n",
    "\n",
    "And go on like this:\n",
    "\n",
    "\\begin{align}\n",
    "v(\\text{Auld Triangle})&=-2+v(\\text{Globetrotter})=-12 \\hspace{0.5cm} \\Leftarrow \\text{optimal choice}\\\\\n",
    "v(\\text{Auld Triangle})&=-4+v(\\text{Black Sheep})=-15\n",
    "\\end{align}\n",
    "\n",
    "\\begin{align}\n",
    "v(\\text{Lötlampe})&=-3+v(\\text{Globetrotter})=-13 \\hspace{0.5cm} \\Leftarrow \\text{optimal choice}\\\\\n",
    "v(\\text{Lötlampe})&=-5+v(\\text{Black Sheep})=-16\n",
    "\\end{align}\n",
    "\n",
    "Finally, we decide where to start:\n",
    "\n",
    "\\begin{align}\n",
    "v(\\text{Home})&=-3+v(\\text{Auld Triangle})=-15 \\\\\n",
    "v(\\text{Home})&=-1+v(\\text{Lötlampe})=-14 \\hspace{0.5cm} \\Leftarrow \\text{optimal choice}\n",
    "\\end{align}\n",
    "\n",
    "\n",
    "i \\ x      | Start  |   A    |  Lö    |   G    |   B    |  Li    |   F    |  End\n",
    "-------- | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ \n",
    "    0    |   0    |   0    |   0    |   0    |   0    |   0    |   0    |   0\n",
    "    1    |   -14  |  -12   |   -13  |   -10  |   -11  |   -6   |   -7   |   0\n",
    "\n",
    "So we have to calculate the value of 5 states (4 pubs and 1 starting node) for both of the possible choices to be made. The 2 states in direct reach of the terminal node do not allow choices. The number of comparisons is therefore given by $N k -1 = 2 \\cdot 3 -1 = 5$ which is much better for large problems than an exhaustive search, if you start clever."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-9b602b091fb02f67",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "\n",
    "\n",
    "## 4) Value Iteration in Stochastic Environments\n",
    "\n",
    "All of the pubs have different special offers on some days of the week.\n",
    "Due to general confusion you have no clue, which day of the week we currently have.\n",
    "You only know, for example, that Globetrotter has one happy-hour-day per week, but Black Sheep has four days per week.\n",
    "So, the chance to get a positive reward in the Black Sheep is higher than in the Globetrotter. \n",
    "\n",
    "To find the best path we can use the Bellman optimality equation we know from the lecture:\n",
    "\n",
    "$v_\\pi(x_k) = \\text{max}_{u_k\\in \\mathcal{U}} \\mathbb{E}\\left[R_{k+1} + \\gamma v_\\pi(X_{k+1}|X_k = x_k, U_k = u_k)\\right]$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-6851b19753ed7028",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## Comparison to lecture:\n",
    "In the tree example from lecture we have deterministic rewards and a stochastic state transition.\n",
    "So $v_\\pi(x_k) = \\text{max}_{u_k\\in \\mathcal{U}} r_x^u + \\gamma \\Sigma_{x_{k+1}\\in \\mathcal{X}}p_{xx'}^u v_\\pi(x_{k+1})$\n",
    "\n",
    "![](TreeExampleVL.PNG)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-b78d669dd6df6f46",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "In our problem we have deterministic state transitions because we reach the bar we plan to visit for sure.\n",
    "But the reward in our case has a stochastic offset.\n",
    "If happy-hour-day (randomly, we do not know the weekday), we get an additional positive reward.\n",
    "The probability to get that is dependent on the number of happy-hour-days per week.\n",
    "For example:\n",
    "\n",
    "![](Stochastic_Rewards.png)\n",
    "\n",
    "As can be seen, in Globetrotter we have in 1 of 7 cases (days) an additional happy-hour-reward and in Black Sheep in 4 of 7 cases.\n",
    "\n",
    "The states are defined in the following order:\n",
    "\n",
    "$\\mathcal{X} = \\left\\lbrace \\begin{matrix}\n",
    "\\text{Start: Home}\\\\\n",
    "\\text{Auld Triangle}\\\\\n",
    "\\text{Lötlampe}\\\\\n",
    "\\text{Globetrotter}\\\\\n",
    "\\text{Black Sheep}\\\\\n",
    "\\text{Limericks}\\\\\n",
    "\\text{Fat Louis}\\\\\n",
    "\\text{End: Home}\\\\\n",
    "\\end{matrix}\n",
    "\\right\\rbrace$\n",
    "\n",
    "The probability to get the positive reward (happy hour) is defined by:\n",
    "\n",
    "$p_{xr_+} = \\left[ \\begin{matrix}\n",
    "\\frac{3}{7} & \\frac{1}{7} & \\frac{1}{7} & \\frac{1}{7} & \\frac{1}{7} & 0 & 0\\\\\n",
    "\\frac{6}{7} & \\frac{4}{7} & \\frac{4}{7} & \\frac{5}{7} & \\frac{5}{7} & 0 & 0\\\\\n",
    "\\end{matrix}\n",
    "\\right]$\n",
    "\n",
    "                    \n",
    "$r_{+} = \\left[ \\begin{matrix}\n",
    "12 & 16 & 16 & 16 & 16 & 0 & 0\\\\\n",
    "6 & 10 & 10 & 8 & 8 & 0 & 0\\\\\n",
    "\\end{matrix}\n",
    "\\right]$  \n",
    "\n",
    "The probability to get the no extra reward is $p_{xr_-} = 1 - p_{xr_+}$.\n",
    "In that case you take the \"no extra reward\" $r_-$ is zero in all cases.\n",
    "\n",
    "$r_{-} = \\left[ \\begin{matrix}\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 0\\\\\n",
    "0 & 0 & 0 & 0 & 0 & 0 & 0\\\\\n",
    "\\end{matrix}\n",
    "\\right]$  \n",
    "\n",
    "\n",
    "The actions to choose are $\\textit{up}$ and $\\textit{down}$ (for states Li and F, $\\textit{up}$ and $\\textit{down}$ mean the same).\n",
    "\n",
    "So if you are at home and you go $\\textit{up}$ you get a fixed reward of $-3$ on the way.\n",
    "With a probability of $p_{x=0,r_+} = \\frac{3}{7}$ there is happy hour in the Auld Triangle and you get an additional reward of $+12$. \n",
    "\n",
    "\n",
    "\n",
    "1. Examine the pseudocode for value iteration as presented in the lecture. Does this pseudocode already contain the concept of a stochastic reward and where do we find it?\n",
    "2. Make use of value iteration to (use $\\gamma = 1$):\n",
    "    1. Find the state value for each state\n",
    "    2. Find the optimal policy\n",
    "3. Check your solution by dynamic programming by hand like in 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-baaebf226260bc67",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "### Pseudocode:\n",
    "***\n",
    "- **input:** Full model of the MDP i.e. $\\left\\langle\\mathcal{X}, \\mathcal{U}, \\mathcal{P}, \\mathcal{R}, \\gamma \\right\\rangle$\n",
    "- **parameter:** $\\delta>0$ as accuracy termination threshold\n",
    "- **init:** $v_0(x_k)\\, \\forall \\, x_k\\in\\mathcal{X}$ arbitrary except $v_0(x_k)=0$ if $x_k$ is terminal\n",
    "- **repeat** \n",
    "    - $\\Delta \\leftarrow 0 $\n",
    "    - **for** $\\forall \\, x_k\\in\\mathcal{X}$\n",
    "        - $\\tilde{v}\\leftarrow \\hat{v}(x_k)$\n",
    "\t\t- $\\hat{v}(x_k)\\leftarrow  \\max_{u_k\\in\\mathcal{U}}\\left(\\mathcal{R}^u_x + \\gamma\\sum_{x_{k+1}\\in\\mathcal{X}}p_{xx'}^u \\hat{v}(x_{k+1})\\right)$\n",
    "\t\t- $\\Delta \\leftarrow \\max\\left(\\Delta, |\\tilde{v}-\\hat{v}(x_k) |\\right)$\n",
    "    - **end**\n",
    "- **until** $\\Delta < \\delta$\n",
    "- **output:** Deterministic policy $\\pi\\approx\\pi^*$, such that\n",
    "\n",
    "$\\pi(x_k)\\leftarrow  \\text{arg} \\, \\text{max}_{u_k\\in\\mathcal{U}}\\left(\\mathcal{R}^u_x + \\gamma\\sum_{x_{k+1}\\in\\mathcal{X}}p_{xx'}^u \\hat{v}(x_{k+1})\\right)$\n",
    "***\n",
    "Value iteration (note: compared to policy iteration, value iteration doesn't require an initial policy but only a state-value guess)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-d75a874a365ec4e3",
     "locked": true,
     "schema_version": 3,
     "solution": false,
     "task": false
    }
   },
   "source": [
    "## 4) Solution \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-2844ac6977528497",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-2.42857143 -5.57142857 -6.57142857 -6.28571429 -7.28571429 -6.         -7.          0.        ]\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "np.set_printoptions(linewidth=100)\n",
    "\n",
    "r_ways = np.array([[-3, -2, -3, -4, -5, -6, -7],\n",
    "                   [-1, -4, -5, -5, -6, -6, -7]]) # fixed rewards for the upwards or downwards path\n",
    "\n",
    "p_xr = np.array([[3/7, 1/7, 1/7, 1/7, 1/7, 0, 0],\n",
    "                 [6/7, 4/7, 4/7, 5/7, 5/7, 0, 0]]) #probability of success for the upwards or downwards path\n",
    "\n",
    "r_happy = np.array([[12, 16, 16, 16, 16, 0, 0],\n",
    "                    [ 6, 10, 10,  8,  8, 0, 0]])\n",
    "\n",
    "expected_rewards = r_ways + p_xr*r_happy + (1-p_xr)*0\n",
    "values = np.zeros([8])\n",
    "\n",
    "\n",
    "delta = 0.1 # lower tolerance boundary\n",
    "\n",
    "### BEGIN SOLUTION\n",
    "\n",
    "error = 100\n",
    "\n",
    "iteration_idx=0\n",
    "while error > delta:\n",
    "    iteration_idx += 1\n",
    "    error = 0\n",
    "    for state_idx in range(len(values)-1):\n",
    "        v_tilde = values[state_idx]\n",
    "        up_value = expected_rewards[0, state_idx] + values[state_idx + (state_idx % 2 + 1)]\n",
    "        if state_idx == 5 or state_idx == 6:\n",
    "            down_value = up_value\n",
    "        else:\n",
    "            down_value = expected_rewards[1, state_idx] + values[state_idx + (state_idx % 2 + 2)]\n",
    "        values[state_idx] = np.max([up_value, down_value])\n",
    "        \n",
    "        error = np.max([error, np.sum(np.abs(v_tilde-values[state_idx]))])        \n",
    "### END SOLUTION\n",
    "print(values)\n",
    "print(iteration_idx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "cell-62c7adb60e0f7d2f",
     "locked": false,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Down', 'Down', 'Down', 'Down', 'Down', 'Graduated! Go home!', 'Graduated! Go home!']\n"
     ]
    }
   ],
   "source": [
    "policy = []\n",
    "for state_idx in range(len(values)-1):     \n",
    "    up_value = expected_rewards[0, state_idx] + values[state_idx + (state_idx % 2 + 1)]\n",
    "    if state_idx == 5 or state_idx == 6:\n",
    "        down_value = up_value\n",
    "    else:\n",
    "        down_value = expected_rewards[1, state_idx] + values[state_idx + (state_idx % 2 + 2)]\n",
    "    if up_value > down_value:\n",
    "        policy.append(\"Up\")\n",
    "    elif up_value < down_value:\n",
    "        policy.append(\"Down\")\n",
    "    else:\n",
    "        policy.append(\"Graduated! Go home!\")        \n",
    "print(policy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": true,
     "grade_id": "cell-ed9723bfe6f22735",
     "locked": false,
     "points": 0,
     "schema_version": 3,
     "solution": true,
     "task": false
    }
   },
   "source": [
    "![](Value_Iteration_Solution.png)"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Create Assignment",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.19"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
